Partition Array Into Two Arrays to Minimize Sum Difference

Statement#

Suppose you are given an array, nums, containing positive numbers. You need to partition the array into two arrays such that the absolute difference between their sums is minimized.

Note: Each element of the nums array should be present in one of the partitioned arrays.

Let’s say you have the following array:

• [2, 3, 1]

The two partitioned arrays with the minimum difference in their sums are:

• $[2, 1], sum = 3$
• $[3], sum = 3$

So, the minimum difference becomes $|3-3| = 0$.

Constraints:

• $1\leq$ nums.length $\leq 900$
• $1\leq$ nums[i] $\leq 10^4$

Examples#

Try it yourself#

Implement your solution in the following playground.

Note: If you clicked the “Submit” button and the code timed out, this means that your solution needs to be optimized in terms of running time.

Hint: Use dynamic programming and see the magic.

Solution#

We will first explore the naive recursive solution to this problem and then see how it can be improved using the 0/1 Knapsack dynamic programming pattern.

Naive approach#

A naive approach is to generate all possible combinations of two arrays from the original array. We then check which combination minimizes the difference between the sums of the two partitioned arrays.

For example, we have the following array of values:

• nums: $[4, 7, 1]$

To find the minimum difference, we try all possible combinations:

• $[4], [7, 1] =>$ Difference $= 4$
• $[7], [4, 1] =>$ Difference $= 2$
• $[1], [4, 7] =>$ Difference $= 10$
• $[7,1], [4] =>$ Difference $= 4$
• $[4,1], [7] =>$ Difference $= 2$
• $[4,7], [1] =>$ Difference $= 10$
• $[4, 7, 1], [] =>$ Difference $= 12$
• $[], [4, 7, 1] =>$ Difference $= 12$

The calculation above shows that we need a recursive solution to make all possible combinations. In other words, we divide the problem into subproblems, and for each array element, we decide whether to place it in the first or second partitioned array. This is done using the following rules:

• Base case: If we reach the end of the array, and there are no elements to add in either of the partitioned arrays, we return the absolute difference between the sums of the two arrays.

• Otherwise, we calculate the difference in the sums of the two arrays for the two scenarios:

  • add the current element to the first partitioned array
  • add it to the second partitioned array

We then select the option that results in the minimum difference.

Let’s implement the algorithm as discussed above:

Note: Please observe that if you include the test case commented out in the driver code, the solution is likely to time out. Try to solve the larger problem using the dynamic programming solutions provided below and see the difference.

Time complexity#

The time complexity of the naive approach is $O(2^n)$, where $n$ is the total number of elements. This is because we have two possible choices for each element, either to include it in the first or the second partitioned array.

Space complexity#

Since we can’t have more than $n$ recursive calls on the call stack at any time, the space complexity of this approach is $O(n)$.

Optimized solution using dynamic programming#

Now, let’s improve the recursive solution using top-down and bottom-up approaches.

Top-down solution#

The top-down solution, commonly known as the memoization technique, is an enhancement of the recursive solution. It overcomes the problem of calculating redundant solutions over and over again by storing them in an array. In the recursive approach, the following three variables kept changing:

• The array index, i.
• The sum of the first partitioned array, sum1.
• The sum of the second partitioned array, sum2.

We will use a 2-D table, dp with i rows, and sum1 + 1 columns to store the result, i.e., the difference between the sums of the partitioned arrays. We haven’t considered sum2 since, for a given i and sum1, sum2 of the remaining numbers will always be the same. At any later time, if we encounter the same subproblem, we can return the stored result from the table with an $O(1)$ look-up instead of re-calculating that subproblem.

Let’s implement the algorithm as discussed above:

Note: Please observe that if you now uncomment the large test case in the driver code, the dynamic programming solution will still work.

Time complexity#

As we avoided redundant calculations by storing all the intermediate results in a 2-D table, the time complexity of this approach is reduced to $O(n \times S)$, where $n$ is the number of elements in the input array, and $S$ is the sum of all the elements.

Space complexity#

We now need $O(n \times S)$ space in memory to store intermediate values.

Bottom-up solution#

The bottom-up solution, also known as the Tabulation technique, is an iterative method of solving dynamic programming problems.

Suppose $S$ is the sum of all the elements in nums. Since we’re taking the absolute difference between the sums of the two partitioned arrays, our minimum difference will always be greater than or equal to $0$. Therefore, to minimize the difference, each partitioned array must have a sum as close to $(S/2)$ as possible. To make things easier, we only need to ensure that the sum in one partitioned array is as close to $(S/2)$ as possible since, then, the remaining sum in the other partitioned array will also become as close to $S/2$ as possible.

We will initialize a 2-D table of size $(n \times [(S/2) + 1])$, where $n$ is the length of nums. This table will have the following properties:

• Each row i represents the index we’re currently on. It ranges from $0$ to $n$.

• Each column s represents the current sum we’re trying to achieve. It ranges from $0$ to $(S/2)$.

We will iterate the table and fill it with either $1$ or $0$ depending on if the current sum s can be achieved from the available elements in the partitioned array or not. This is done based on the following rules:

• We exclude nums[i] from the partitioned array and check whether the sum s can be formed from its previous elements.

if dp[i - 1][s]:
        dp[i][s] = dp[i - 1][s]

• We include nums[i] in the partitioned array and check whether the sum s can now be formed from its current elements.

 elif s >= nums[i]:
        dp[i][s] = dp[i - 1][s - nums[i]]

• If neither one of the above two conditions is true, the sum s can not be formed using nums[i]:

else:
    dp[i][s] = 0

After the 2-D table has been filled completely, we will traverse its last row from right to left to find the sum closest to $(S/2)$ that the partitioned array can contain. Whenever we find an entry that is $1$, the value of i at that entry will be the partitioned array sum. Using this sum we find the sum in the other partitioned array and then calculate their absolute difference.

Let’s look at the following illustration to get a better understanding of the solution:

Let’s implement the algorithm as discussed above:

Note: Please observe that if you now uncomment the large test case in the driver code, the dynamic programming solution will still work.

Time complexity#

As we created a 2-D table to store the results of sub-problems that would be used later on, therefore, the time complexity of this approach will also be $O(n \times [(S/2) + 1])$.

Space complexity#

We need $O(n \times [(S/2) + 1])$ space in memory to store the intermediate values.

Can we do better?#

You must have noticed in the above algorithm that to fill up a row, we only require the previous row’s values; that is, for filling the row against the $i^{th}$ element, we require the values from the previous row representing the $(i-1)^{th}$ element. Therefore, there is no point in storing the previous $(i - 2)$ rows.

We can further improve this approach by using a lookup array of length $[(S/2) + 1])$ instead of creating a table. Next, we update this array for each element using the same calculation which we used earlier.

The time complexity would remain the same, $O(n \times [(S/2) + 1])$ , because we still have to do the calculation for each element. The space complexity, however, reduces to $O((S/2) + 1)$ since we are only maintaining an array of size $(S/2) + 1$.